/*
 * Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved.
 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 */

package javax.swing.tree;
// ISSUE: this class depends on nothing in AWT -- move to java.util?

import java.beans.Transient;
import java.io.*;
import java.util.*;


/**
 * A <code>DefaultMutableTreeNode</code> is a general-purpose node in a tree data
 * structure.
 * For examples of using default mutable tree nodes, see
 * <a
 * href="https://docs.oracle.com/javase/tutorial/uiswing/components/tree.html">How to Use Trees</a>
 * in <em>The Java Tutorial.</em>
 *
 * <p>
 *
 * A tree node may have at most one parent and 0 or more children.
 * <code>DefaultMutableTreeNode</code> provides operations for examining and modifying a
 * node's parent and children and also operations for examining the tree that
 * the node is a part of.  A node's tree is the set of all nodes that can be
 * reached by starting at the node and following all the possible links to
 * parents and children.  A node with no parent is the root of its tree; a
 * node with no children is a leaf.  A tree may consist of many subtrees,
 * each node acting as the root for its own subtree.
 * <p>
 * This class provides enumerations for efficiently traversing a tree or
 * subtree in various orders or for following the path between two nodes.
 * A <code>DefaultMutableTreeNode</code> may also hold a reference to a user object, the
 * use of which is left to the user.  Asking a <code>DefaultMutableTreeNode</code> for its
 * string representation with <code>toString()</code> returns the string
 * representation of its user object.
 * <p>
 * <b>This is not a thread safe class.</b>If you intend to use
 * a DefaultMutableTreeNode (or a tree of TreeNodes) in more than one thread, you
 * need to do your own synchronizing. A good convention to adopt is
 * synchronizing on the root node of a tree.
 * <p>
 * While DefaultMutableTreeNode implements the MutableTreeNode interface and
 * will allow you to add in any implementation of MutableTreeNode not all
 * of the methods in DefaultMutableTreeNode will be applicable to all
 * MutableTreeNodes implementations. Especially with some of the enumerations
 * that are provided, using some of these methods assumes the
 * DefaultMutableTreeNode contains only DefaultMutableNode instances. All
 * of the TreeNode/MutableTreeNode methods will behave as defined no
 * matter what implementations are added.
 *
 * <p>
 * <strong>Warning:</strong>
 * Serialized objects of this class will not be compatible with
 * future Swing releases. The current serialization support is
 * appropriate for short term storage or RMI between applications running
 * the same version of Swing.  As of 1.4, support for long term storage
 * of all JavaBeans&trade;
 * has been added to the <code>java.beans</code> package.
 * Please see {@link java.beans.XMLEncoder}.
 *
 * @author Rob Davis
 * @see MutableTreeNode
 */
public class DefaultMutableTreeNode implements Cloneable,
    MutableTreeNode, Serializable {

  private static final long serialVersionUID = -4298474751201349152L;

  /**
   * An enumeration that is always empty. This is used when an enumeration
   * of a leaf node's children is requested.
   */
  static public final Enumeration<TreeNode> EMPTY_ENUMERATION
      = Collections.emptyEnumeration();

  /**
   * this node's parent, or null if this node has no parent
   */
  protected MutableTreeNode parent;

  /**
   * array of children, may be null if this node has no children
   */
  protected Vector children;

  /**
   * optional user object
   */
  transient protected Object userObject;

  /**
   * true if the node is able to have children
   */
  protected boolean allowsChildren;


  /**
   * Creates a tree node that has no parent and no children, but which
   * allows children.
   */
  public DefaultMutableTreeNode() {
    this(null);
  }

  /**
   * Creates a tree node with no parent, no children, but which allows
   * children, and initializes it with the specified user object.
   *
   * @param userObject an Object provided by the user that constitutes the node's data
   */
  public DefaultMutableTreeNode(Object userObject) {
    this(userObject, true);
  }

  /**
   * Creates a tree node with no parent, no children, initialized with
   * the specified user object, and that allows children only if
   * specified.
   *
   * @param userObject an Object provided by the user that constitutes the node's data
   * @param allowsChildren if true, the node is allowed to have child nodes -- otherwise, it is
   * always a leaf node
   */
  public DefaultMutableTreeNode(Object userObject, boolean allowsChildren) {
    super();
    parent = null;
    this.allowsChildren = allowsChildren;
    this.userObject = userObject;
  }

  //
  //  Primitives
  //

  /**
   * Removes <code>newChild</code> from its present parent (if it has a
   * parent), sets the child's parent to this node, and then adds the child
   * to this node's child array at index <code>childIndex</code>.
   * <code>newChild</code> must not be null and must not be an ancestor of
   * this node.
   *
   * @param newChild the MutableTreeNode to insert under this node
   * @param childIndex the index in this node's child array where this node is to be inserted
   * @throws ArrayIndexOutOfBoundsException if <code>childIndex</code> is out of bounds
   * @throws IllegalArgumentException if <code>newChild</code> is null or is an ancestor of this
   * node
   * @throws IllegalStateException if this node does not allow children
   * @see #isNodeDescendant
   */
  public void insert(MutableTreeNode newChild, int childIndex) {
    if (!allowsChildren) {
      throw new IllegalStateException("node does not allow children");
    } else if (newChild == null) {
      throw new IllegalArgumentException("new child is null");
    } else if (isNodeAncestor(newChild)) {
      throw new IllegalArgumentException("new child is an ancestor");
    }

    MutableTreeNode oldParent = (MutableTreeNode) newChild.getParent();

    if (oldParent != null) {
      oldParent.remove(newChild);
    }
    newChild.setParent(this);
    if (children == null) {
      children = new Vector();
    }
    children.insertElementAt(newChild, childIndex);
  }

  /**
   * Removes the child at the specified index from this node's children
   * and sets that node's parent to null. The child node to remove
   * must be a <code>MutableTreeNode</code>.
   *
   * @param childIndex the index in this node's child array of the child to remove
   * @throws ArrayIndexOutOfBoundsException if <code>childIndex</code> is out of bounds
   */
  public void remove(int childIndex) {
    MutableTreeNode child = (MutableTreeNode) getChildAt(childIndex);
    children.removeElementAt(childIndex);
    child.setParent(null);
  }

  /**
   * Sets this node's parent to <code>newParent</code> but does not
   * change the parent's child array.  This method is called from
   * <code>insert()</code> and <code>remove()</code> to
   * reassign a child's parent, it should not be messaged from anywhere
   * else.
   *
   * @param newParent this node's new parent
   */
  @Transient
  public void setParent(MutableTreeNode newParent) {
    parent = newParent;
  }

  /**
   * Returns this node's parent or null if this node has no parent.
   *
   * @return this node's parent TreeNode, or null if this node has no parent
   */
  public TreeNode getParent() {
    return parent;
  }

  /**
   * Returns the child at the specified index in this node's child array.
   *
   * @param index an index into this node's child array
   * @return the TreeNode in this node's child array at  the specified index
   * @throws ArrayIndexOutOfBoundsException if <code>index</code> is out of bounds
   */
  public TreeNode getChildAt(int index) {
    if (children == null) {
      throw new ArrayIndexOutOfBoundsException("node has no children");
    }
    return (TreeNode) children.elementAt(index);
  }

  /**
   * Returns the number of children of this node.
   *
   * @return an int giving the number of children of this node
   */
  public int getChildCount() {
    if (children == null) {
      return 0;
    } else {
      return children.size();
    }
  }

  /**
   * Returns the index of the specified child in this node's child array.
   * If the specified node is not a child of this node, returns
   * <code>-1</code>.  This method performs a linear search and is O(n)
   * where n is the number of children.
   *
   * @param aChild the TreeNode to search for among this node's children
   * @return an int giving the index of the node in this node's child array, or <code>-1</code> if
   * the specified node is a not a child of this node
   * @throws IllegalArgumentException if <code>aChild</code> is null
   */
  public int getIndex(TreeNode aChild) {
    if (aChild == null) {
      throw new IllegalArgumentException("argument is null");
    }

    if (!isNodeChild(aChild)) {
      return -1;
    }
    return children.indexOf(aChild);        // linear search
  }

  /**
   * Creates and returns a forward-order enumeration of this node's
   * children.  Modifying this node's child array invalidates any child
   * enumerations created before the modification.
   *
   * @return an Enumeration of this node's children
   */
  public Enumeration children() {
    if (children == null) {
      return EMPTY_ENUMERATION;
    } else {
      return children.elements();
    }
  }

  /**
   * Determines whether or not this node is allowed to have children.
   * If <code>allows</code> is false, all of this node's children are
   * removed.
   * <p>
   * Note: By default, a node allows children.
   *
   * @param allows true if this node is allowed to have children
   */
  public void setAllowsChildren(boolean allows) {
    if (allows != allowsChildren) {
      allowsChildren = allows;
      if (!allowsChildren) {
        removeAllChildren();
      }
    }
  }

  /**
   * Returns true if this node is allowed to have children.
   *
   * @return true if this node allows children, else false
   */
  public boolean getAllowsChildren() {
    return allowsChildren;
  }

  /**
   * Sets the user object for this node to <code>userObject</code>.
   *
   * @param userObject the Object that constitutes this node's user-specified data
   * @see #getUserObject
   * @see #toString
   */
  public void setUserObject(Object userObject) {
    this.userObject = userObject;
  }

  /**
   * Returns this node's user object.
   *
   * @return the Object stored at this node by the user
   * @see #setUserObject
   * @see #toString
   */
  public Object getUserObject() {
    return userObject;
  }

  //
  //  Derived methods
  //

  /**
   * Removes the subtree rooted at this node from the tree, giving this
   * node a null parent.  Does nothing if this node is the root of its
   * tree.
   */
  public void removeFromParent() {
    MutableTreeNode parent = (MutableTreeNode) getParent();
    if (parent != null) {
      parent.remove(this);
    }
  }

  /**
   * Removes <code>aChild</code> from this node's child array, giving it a
   * null parent.
   *
   * @param aChild a child of this node to remove
   * @throws IllegalArgumentException if <code>aChild</code> is null or is not a child of this node
   */
  public void remove(MutableTreeNode aChild) {
    if (aChild == null) {
      throw new IllegalArgumentException("argument is null");
    }

    if (!isNodeChild(aChild)) {
      throw new IllegalArgumentException("argument is not a child");
    }
    remove(getIndex(aChild));       // linear search
  }

  /**
   * Removes all of this node's children, setting their parents to null.
   * If this node has no children, this method does nothing.
   */
  public void removeAllChildren() {
    for (int i = getChildCount() - 1; i >= 0; i--) {
      remove(i);
    }
  }

  /**
   * Removes <code>newChild</code> from its parent and makes it a child of
   * this node by adding it to the end of this node's child array.
   *
   * @param newChild node to add as a child of this node
   * @throws IllegalArgumentException if <code>newChild</code> is null
   * @throws IllegalStateException if this node does not allow children
   * @see #insert
   */
  public void add(MutableTreeNode newChild) {
    if (newChild != null && newChild.getParent() == this) {
      insert(newChild, getChildCount() - 1);
    } else {
      insert(newChild, getChildCount());
    }
  }

  //
  //  Tree Queries
  //

  /**
   * Returns true if <code>anotherNode</code> is an ancestor of this node
   * -- if it is this node, this node's parent, or an ancestor of this
   * node's parent.  (Note that a node is considered an ancestor of itself.)
   * If <code>anotherNode</code> is null, this method returns false.  This
   * operation is at worst O(h) where h is the distance from the root to
   * this node.
   *
   * @param anotherNode node to test as an ancestor of this node
   * @return true if this node is a descendant of <code>anotherNode</code>
   * @see #isNodeDescendant
   * @see #getSharedAncestor
   */
  public boolean isNodeAncestor(TreeNode anotherNode) {
    if (anotherNode == null) {
      return false;
    }

    TreeNode ancestor = this;

    do {
      if (ancestor == anotherNode) {
        return true;
      }
    } while ((ancestor = ancestor.getParent()) != null);

    return false;
  }

  /**
   * Returns true if <code>anotherNode</code> is a descendant of this node
   * -- if it is this node, one of this node's children, or a descendant of
   * one of this node's children.  Note that a node is considered a
   * descendant of itself.  If <code>anotherNode</code> is null, returns
   * false.  This operation is at worst O(h) where h is the distance from the
   * root to <code>anotherNode</code>.
   *
   * @param anotherNode node to test as descendant of this node
   * @return true if this node is an ancestor of <code>anotherNode</code>
   * @see #isNodeAncestor
   * @see #getSharedAncestor
   */
  public boolean isNodeDescendant(DefaultMutableTreeNode anotherNode) {
    if (anotherNode == null) {
      return false;
    }

    return anotherNode.isNodeAncestor(this);
  }

  /**
   * Returns the nearest common ancestor to this node and <code>aNode</code>.
   * Returns null, if no such ancestor exists -- if this node and
   * <code>aNode</code> are in different trees or if <code>aNode</code> is
   * null.  A node is considered an ancestor of itself.
   *
   * @param aNode node to find common ancestor with
   * @return nearest ancestor common to this node and <code>aNode</code>, or null if none
   * @see #isNodeAncestor
   * @see #isNodeDescendant
   */
  public TreeNode getSharedAncestor(DefaultMutableTreeNode aNode) {
    if (aNode == this) {
      return this;
    } else if (aNode == null) {
      return null;
    }

    int level1, level2, diff;
    TreeNode node1, node2;

    level1 = getLevel();
    level2 = aNode.getLevel();

    if (level2 > level1) {
      diff = level2 - level1;
      node1 = aNode;
      node2 = this;
    } else {
      diff = level1 - level2;
      node1 = this;
      node2 = aNode;
    }

    // Go up the tree until the nodes are at the same level
    while (diff > 0) {
      node1 = node1.getParent();
      diff--;
    }

    // Move up the tree until we find a common ancestor.  Since we know
    // that both nodes are at the same level, we won't cross paths
    // unknowingly (if there is a common ancestor, both nodes hit it in
    // the same iteration).

    do {
      if (node1 == node2) {
        return node1;
      }
      node1 = node1.getParent();
      node2 = node2.getParent();
    } while (node1 != null);// only need to check one -- they're at the
    // same level so if one is null, the other is

    if (node1 != null || node2 != null) {
      throw new Error("nodes should be null");
    }

    return null;
  }


  /**
   * Returns true if and only if <code>aNode</code> is in the same tree
   * as this node.  Returns false if <code>aNode</code> is null.
   *
   * @return true if <code>aNode</code> is in the same tree as this node; false if
   * <code>aNode</code> is null
   * @see #getSharedAncestor
   * @see #getRoot
   */
  public boolean isNodeRelated(DefaultMutableTreeNode aNode) {
    return (aNode != null) && (getRoot() == aNode.getRoot());
  }


  /**
   * Returns the depth of the tree rooted at this node -- the longest
   * distance from this node to a leaf.  If this node has no children,
   * returns 0.  This operation is much more expensive than
   * <code>getLevel()</code> because it must effectively traverse the entire
   * tree rooted at this node.
   *
   * @return the depth of the tree whose root is this node
   * @see #getLevel
   */
  public int getDepth() {
    Object last = null;
    Enumeration enum_ = breadthFirstEnumeration();

    while (enum_.hasMoreElements()) {
      last = enum_.nextElement();
    }

    if (last == null) {
      throw new Error("nodes should be null");
    }

    return ((DefaultMutableTreeNode) last).getLevel() - getLevel();
  }


  /**
   * Returns the number of levels above this node -- the distance from
   * the root to this node.  If this node is the root, returns 0.
   *
   * @return the number of levels above this node
   * @see #getDepth
   */
  public int getLevel() {
    TreeNode ancestor;
    int levels = 0;

    ancestor = this;
    while ((ancestor = ancestor.getParent()) != null) {
      levels++;
    }

    return levels;
  }


  /**
   * Returns the path from the root, to get to this node.  The last
   * element in the path is this node.
   *
   * @return an array of TreeNode objects giving the path, where the first element in the path is
   * the root and the last element is this node.
   */
  public TreeNode[] getPath() {
    return getPathToRoot(this, 0);
  }

  /**
   * Builds the parents of node up to and including the root node,
   * where the original node is the last element in the returned array.
   * The length of the returned array gives the node's depth in the
   * tree.
   *
   * @param aNode the TreeNode to get the path for
   * @param depth an int giving the number of steps already taken towards the root (on recursive
   * calls), used to size the returned array
   * @return an array of TreeNodes giving the path from the root to the specified node
   */
  protected TreeNode[] getPathToRoot(TreeNode aNode, int depth) {
    TreeNode[] retNodes;

        /* Check for null, in case someone passed in a null node, or
           they passed in an element that isn't rooted at root. */
    if (aNode == null) {
      if (depth == 0) {
        return null;
      } else {
        retNodes = new TreeNode[depth];
      }
    } else {
      depth++;
      retNodes = getPathToRoot(aNode.getParent(), depth);
      retNodes[retNodes.length - depth] = aNode;
    }
    return retNodes;
  }

  /**
   * Returns the user object path, from the root, to get to this node.
   * If some of the TreeNodes in the path have null user objects, the
   * returned path will contain nulls.
   */
  public Object[] getUserObjectPath() {
    TreeNode[] realPath = getPath();
    Object[] retPath = new Object[realPath.length];

    for (int counter = 0; counter < realPath.length; counter++) {
      retPath[counter] = ((DefaultMutableTreeNode) realPath[counter])
          .getUserObject();
    }
    return retPath;
  }

  /**
   * Returns the root of the tree that contains this node.  The root is
   * the ancestor with a null parent.
   *
   * @return the root of the tree that contains this node
   * @see #isNodeAncestor
   */
  public TreeNode getRoot() {
    TreeNode ancestor = this;
    TreeNode previous;

    do {
      previous = ancestor;
      ancestor = ancestor.getParent();
    } while (ancestor != null);

    return previous;
  }


  /**
   * Returns true if this node is the root of the tree.  The root is
   * the only node in the tree with a null parent; every tree has exactly
   * one root.
   *
   * @return true if this node is the root of its tree
   */
  public boolean isRoot() {
    return getParent() == null;
  }


  /**
   * Returns the node that follows this node in a preorder traversal of this
   * node's tree.  Returns null if this node is the last node of the
   * traversal.  This is an inefficient way to traverse the entire tree; use
   * an enumeration, instead.
   *
   * @return the node that follows this node in a preorder traversal, or null if this node is last
   * @see #preorderEnumeration
   */
  public DefaultMutableTreeNode getNextNode() {
    if (getChildCount() == 0) {
      // No children, so look for nextSibling
      DefaultMutableTreeNode nextSibling = getNextSibling();

      if (nextSibling == null) {
        DefaultMutableTreeNode aNode = (DefaultMutableTreeNode) getParent();

        do {
          if (aNode == null) {
            return null;
          }

          nextSibling = aNode.getNextSibling();
          if (nextSibling != null) {
            return nextSibling;
          }

          aNode = (DefaultMutableTreeNode) aNode.getParent();
        } while (true);
      } else {
        return nextSibling;
      }
    } else {
      return (DefaultMutableTreeNode) getChildAt(0);
    }
  }


  /**
   * Returns the node that precedes this node in a preorder traversal of
   * this node's tree.  Returns <code>null</code> if this node is the
   * first node of the traversal -- the root of the tree.
   * This is an inefficient way to
   * traverse the entire tree; use an enumeration, instead.
   *
   * @return the node that precedes this node in a preorder traversal, or null if this node is the
   * first
   * @see #preorderEnumeration
   */
  public DefaultMutableTreeNode getPreviousNode() {
    DefaultMutableTreeNode previousSibling;
    DefaultMutableTreeNode myParent = (DefaultMutableTreeNode) getParent();

    if (myParent == null) {
      return null;
    }

    previousSibling = getPreviousSibling();

    if (previousSibling != null) {
      if (previousSibling.getChildCount() == 0) {
        return previousSibling;
      } else {
        return previousSibling.getLastLeaf();
      }
    } else {
      return myParent;
    }
  }

  /**
   * Creates and returns an enumeration that traverses the subtree rooted at
   * this node in preorder.  The first node returned by the enumeration's
   * <code>nextElement()</code> method is this node.<P>
   *
   * Modifying the tree by inserting, removing, or moving a node invalidates
   * any enumerations created before the modification.
   *
   * @return an enumeration for traversing the tree in preorder
   * @see #postorderEnumeration
   */
  public Enumeration preorderEnumeration() {
    return new PreorderEnumeration(this);
  }

  /**
   * Creates and returns an enumeration that traverses the subtree rooted at
   * this node in postorder.  The first node returned by the enumeration's
   * <code>nextElement()</code> method is the leftmost leaf.  This is the
   * same as a depth-first traversal.<P>
   *
   * Modifying the tree by inserting, removing, or moving a node invalidates
   * any enumerations created before the modification.
   *
   * @return an enumeration for traversing the tree in postorder
   * @see #depthFirstEnumeration
   * @see #preorderEnumeration
   */
  public Enumeration postorderEnumeration() {
    return new PostorderEnumeration(this);
  }

  /**
   * Creates and returns an enumeration that traverses the subtree rooted at
   * this node in breadth-first order.  The first node returned by the
   * enumeration's <code>nextElement()</code> method is this node.<P>
   *
   * Modifying the tree by inserting, removing, or moving a node invalidates
   * any enumerations created before the modification.
   *
   * @return an enumeration for traversing the tree in breadth-first order
   * @see #depthFirstEnumeration
   */
  public Enumeration breadthFirstEnumeration() {
    return new BreadthFirstEnumeration(this);
  }

  /**
   * Creates and returns an enumeration that traverses the subtree rooted at
   * this node in depth-first order.  The first node returned by the
   * enumeration's <code>nextElement()</code> method is the leftmost leaf.
   * This is the same as a postorder traversal.<P>
   *
   * Modifying the tree by inserting, removing, or moving a node invalidates
   * any enumerations created before the modification.
   *
   * @return an enumeration for traversing the tree in depth-first order
   * @see #breadthFirstEnumeration
   * @see #postorderEnumeration
   */
  public Enumeration depthFirstEnumeration() {
    return postorderEnumeration();
  }

  /**
   * Creates and returns an enumeration that follows the path from
   * <code>ancestor</code> to this node.  The enumeration's
   * <code>nextElement()</code> method first returns <code>ancestor</code>,
   * then the child of <code>ancestor</code> that is an ancestor of this
   * node, and so on, and finally returns this node.  Creation of the
   * enumeration is O(m) where m is the number of nodes between this node
   * and <code>ancestor</code>, inclusive.  Each <code>nextElement()</code>
   * message is O(1).<P>
   *
   * Modifying the tree by inserting, removing, or moving a node invalidates
   * any enumerations created before the modification.
   *
   * @return an enumeration for following the path from an ancestor of this node to this one
   * @throws IllegalArgumentException if <code>ancestor</code> is not an ancestor of this node
   * @see #isNodeAncestor
   * @see #isNodeDescendant
   */
  public Enumeration pathFromAncestorEnumeration(TreeNode ancestor) {
    return new PathBetweenNodesEnumeration(ancestor, this);
  }

  //
  //  Child Queries
  //

  /**
   * Returns true if <code>aNode</code> is a child of this node.  If
   * <code>aNode</code> is null, this method returns false.
   *
   * @return true if <code>aNode</code> is a child of this node; false if <code>aNode</code> is null
   */
  public boolean isNodeChild(TreeNode aNode) {
    boolean retval;

    if (aNode == null) {
      retval = false;
    } else {
      if (getChildCount() == 0) {
        retval = false;
      } else {
        retval = (aNode.getParent() == this);
      }
    }

    return retval;
  }


  /**
   * Returns this node's first child.  If this node has no children,
   * throws NoSuchElementException.
   *
   * @return the first child of this node
   * @throws NoSuchElementException if this node has no children
   */
  public TreeNode getFirstChild() {
    if (getChildCount() == 0) {
      throw new NoSuchElementException("node has no children");
    }
    return getChildAt(0);
  }


  /**
   * Returns this node's last child.  If this node has no children,
   * throws NoSuchElementException.
   *
   * @return the last child of this node
   * @throws NoSuchElementException if this node has no children
   */
  public TreeNode getLastChild() {
    if (getChildCount() == 0) {
      throw new NoSuchElementException("node has no children");
    }
    return getChildAt(getChildCount() - 1);
  }


  /**
   * Returns the child in this node's child array that immediately
   * follows <code>aChild</code>, which must be a child of this node.  If
   * <code>aChild</code> is the last child, returns null.  This method
   * performs a linear search of this node's children for
   * <code>aChild</code> and is O(n) where n is the number of children; to
   * traverse the entire array of children, use an enumeration instead.
   *
   * @return the child of this node that immediately follows <code>aChild</code>
   * @throws IllegalArgumentException if <code>aChild</code> is null or is not a child of this node
   * @see #children
   */
  public TreeNode getChildAfter(TreeNode aChild) {
    if (aChild == null) {
      throw new IllegalArgumentException("argument is null");
    }

    int index = getIndex(aChild);           // linear search

    if (index == -1) {
      throw new IllegalArgumentException("node is not a child");
    }

    if (index < getChildCount() - 1) {
      return getChildAt(index + 1);
    } else {
      return null;
    }
  }


  /**
   * Returns the child in this node's child array that immediately
   * precedes <code>aChild</code>, which must be a child of this node.  If
   * <code>aChild</code> is the first child, returns null.  This method
   * performs a linear search of this node's children for <code>aChild</code>
   * and is O(n) where n is the number of children.
   *
   * @return the child of this node that immediately precedes <code>aChild</code>
   * @throws IllegalArgumentException if <code>aChild</code> is null or is not a child of this node
   */
  public TreeNode getChildBefore(TreeNode aChild) {
    if (aChild == null) {
      throw new IllegalArgumentException("argument is null");
    }

    int index = getIndex(aChild);           // linear search

    if (index == -1) {
      throw new IllegalArgumentException("argument is not a child");
    }

    if (index > 0) {
      return getChildAt(index - 1);
    } else {
      return null;
    }
  }

  //
  //  Sibling Queries
  //


  /**
   * Returns true if <code>anotherNode</code> is a sibling of (has the
   * same parent as) this node.  A node is its own sibling.  If
   * <code>anotherNode</code> is null, returns false.
   *
   * @param anotherNode node to test as sibling of this node
   * @return true if <code>anotherNode</code> is a sibling of this node
   */
  public boolean isNodeSibling(TreeNode anotherNode) {
    boolean retval;

    if (anotherNode == null) {
      retval = false;
    } else if (anotherNode == this) {
      retval = true;
    } else {
      TreeNode myParent = getParent();
      retval = (myParent != null && myParent == anotherNode.getParent());

      if (retval && !((DefaultMutableTreeNode) getParent())
          .isNodeChild(anotherNode)) {
        throw new Error("sibling has different parent");
      }
    }

    return retval;
  }


  /**
   * Returns the number of siblings of this node.  A node is its own sibling
   * (if it has no parent or no siblings, this method returns
   * <code>1</code>).
   *
   * @return the number of siblings of this node
   */
  public int getSiblingCount() {
    TreeNode myParent = getParent();

    if (myParent == null) {
      return 1;
    } else {
      return myParent.getChildCount();
    }
  }


  /**
   * Returns the next sibling of this node in the parent's children array.
   * Returns null if this node has no parent or is the parent's last child.
   * This method performs a linear search that is O(n) where n is the number
   * of children; to traverse the entire array, use the parent's child
   * enumeration instead.
   *
   * @return the sibling of this node that immediately follows this node
   * @see #children
   */
  public DefaultMutableTreeNode getNextSibling() {
    DefaultMutableTreeNode retval;

    DefaultMutableTreeNode myParent = (DefaultMutableTreeNode) getParent();

    if (myParent == null) {
      retval = null;
    } else {
      retval = (DefaultMutableTreeNode) myParent.getChildAfter(this);      // linear search
    }

    if (retval != null && !isNodeSibling(retval)) {
      throw new Error("child of parent is not a sibling");
    }

    return retval;
  }


  /**
   * Returns the previous sibling of this node in the parent's children
   * array.  Returns null if this node has no parent or is the parent's
   * first child.  This method performs a linear search that is O(n) where n
   * is the number of children.
   *
   * @return the sibling of this node that immediately precedes this node
   */
  public DefaultMutableTreeNode getPreviousSibling() {
    DefaultMutableTreeNode retval;

    DefaultMutableTreeNode myParent = (DefaultMutableTreeNode) getParent();

    if (myParent == null) {
      retval = null;
    } else {
      retval = (DefaultMutableTreeNode) myParent.getChildBefore(this);     // linear search
    }

    if (retval != null && !isNodeSibling(retval)) {
      throw new Error("child of parent is not a sibling");
    }

    return retval;
  }

  //
  //  Leaf Queries
  //

  /**
   * Returns true if this node has no children.  To distinguish between
   * nodes that have no children and nodes that <i>cannot</i> have
   * children (e.g. to distinguish files from empty directories), use this
   * method in conjunction with <code>getAllowsChildren</code>
   *
   * @return true if this node has no children
   * @see #getAllowsChildren
   */
  public boolean isLeaf() {
    return (getChildCount() == 0);
  }


  /**
   * Finds and returns the first leaf that is a descendant of this node --
   * either this node or its first child's first leaf.
   * Returns this node if it is a leaf.
   *
   * @return the first leaf in the subtree rooted at this node
   * @see #isLeaf
   * @see #isNodeDescendant
   */
  public DefaultMutableTreeNode getFirstLeaf() {
    DefaultMutableTreeNode node = this;

    while (!node.isLeaf()) {
      node = (DefaultMutableTreeNode) node.getFirstChild();
    }

    return node;
  }


  /**
   * Finds and returns the last leaf that is a descendant of this node --
   * either this node or its last child's last leaf.
   * Returns this node if it is a leaf.
   *
   * @return the last leaf in the subtree rooted at this node
   * @see #isLeaf
   * @see #isNodeDescendant
   */
  public DefaultMutableTreeNode getLastLeaf() {
    DefaultMutableTreeNode node = this;

    while (!node.isLeaf()) {
      node = (DefaultMutableTreeNode) node.getLastChild();
    }

    return node;
  }


  /**
   * Returns the leaf after this node or null if this node is the
   * last leaf in the tree.
   * <p>
   * In this implementation of the <code>MutableNode</code> interface,
   * this operation is very inefficient. In order to determine the
   * next node, this method first performs a linear search in the
   * parent's child-list in order to find the current node.
   * <p>
   * That implementation makes the operation suitable for short
   * traversals from a known position. But to traverse all of the
   * leaves in the tree, you should use <code>depthFirstEnumeration</code>
   * to enumerate the nodes in the tree and use <code>isLeaf</code>
   * on each node to determine which are leaves.
   *
   * @return returns the next leaf past this node
   * @see #depthFirstEnumeration
   * @see #isLeaf
   */
  public DefaultMutableTreeNode getNextLeaf() {
    DefaultMutableTreeNode nextSibling;
    DefaultMutableTreeNode myParent = (DefaultMutableTreeNode) getParent();

    if (myParent == null) {
      return null;
    }

    nextSibling = getNextSibling(); // linear search

    if (nextSibling != null) {
      return nextSibling.getFirstLeaf();
    }

    return myParent.getNextLeaf();  // tail recursion
  }


  /**
   * Returns the leaf before this node or null if this node is the
   * first leaf in the tree.
   * <p>
   * In this implementation of the <code>MutableNode</code> interface,
   * this operation is very inefficient. In order to determine the
   * previous node, this method first performs a linear search in the
   * parent's child-list in order to find the current node.
   * <p>
   * That implementation makes the operation suitable for short
   * traversals from a known position. But to traverse all of the
   * leaves in the tree, you should use <code>depthFirstEnumeration</code>
   * to enumerate the nodes in the tree and use <code>isLeaf</code>
   * on each node to determine which are leaves.
   *
   * @return returns the leaf before this node
   * @see #depthFirstEnumeration
   * @see #isLeaf
   */
  public DefaultMutableTreeNode getPreviousLeaf() {
    DefaultMutableTreeNode previousSibling;
    DefaultMutableTreeNode myParent = (DefaultMutableTreeNode) getParent();

    if (myParent == null) {
      return null;
    }

    previousSibling = getPreviousSibling(); // linear search

    if (previousSibling != null) {
      return previousSibling.getLastLeaf();
    }

    return myParent.getPreviousLeaf();              // tail recursion
  }


  /**
   * Returns the total number of leaves that are descendants of this node.
   * If this node is a leaf, returns <code>1</code>.  This method is O(n)
   * where n is the number of descendants of this node.
   *
   * @return the number of leaves beneath this node
   * @see #isNodeAncestor
   */
  public int getLeafCount() {
    int count = 0;

    TreeNode node;
    Enumeration enum_ = breadthFirstEnumeration(); // order matters not

    while (enum_.hasMoreElements()) {
      node = (TreeNode) enum_.nextElement();
      if (node.isLeaf()) {
        count++;
      }
    }

    if (count < 1) {
      throw new Error("tree has zero leaves");
    }

    return count;
  }

  //
  //  Overrides
  //

  /**
   * Returns the result of sending <code>toString()</code> to this node's
   * user object, or the empty string if the node has no user object.
   *
   * @see #getUserObject
   */
  public String toString() {
    if (userObject == null) {
      return "";
    } else {
      return userObject.toString();
    }
  }

  /**
   * Overridden to make clone public.  Returns a shallow copy of this node;
   * the new node has no parent or children and has a reference to the same
   * user object, if any.
   *
   * @return a copy of this node
   */
  public Object clone() {
    DefaultMutableTreeNode newNode;

    try {
      newNode = (DefaultMutableTreeNode) super.clone();

      // shallow copy -- the new node has no parent or children
      newNode.children = null;
      newNode.parent = null;

    } catch (CloneNotSupportedException e) {
      // Won't happen because we implement Cloneable
      throw new Error(e.toString());
    }

    return newNode;
  }


  // Serialization support.
  private void writeObject(ObjectOutputStream s) throws IOException {
    Object[] tValues;

    s.defaultWriteObject();
    // Save the userObject, if its Serializable.
    if (userObject != null && userObject instanceof Serializable) {
      tValues = new Object[2];
      tValues[0] = "userObject";
      tValues[1] = userObject;
    } else {
      tValues = new Object[0];
    }
    s.writeObject(tValues);
  }

  private void readObject(ObjectInputStream s)
      throws IOException, ClassNotFoundException {
    Object[] tValues;

    s.defaultReadObject();

    tValues = (Object[]) s.readObject();

    if (tValues.length > 0 && tValues[0].equals("userObject")) {
      userObject = tValues[1];
    }
  }

  private final class PreorderEnumeration implements Enumeration<TreeNode> {

    private final Stack<Enumeration> stack = new Stack<Enumeration>();

    public PreorderEnumeration(TreeNode rootNode) {
      super();
      Vector<TreeNode> v = new Vector<TreeNode>(1);
      v.addElement(rootNode);     // PENDING: don't really need a vector
      stack.push(v.elements());
    }

    public boolean hasMoreElements() {
      return (!stack.empty() && stack.peek().hasMoreElements());
    }

    public TreeNode nextElement() {
      Enumeration enumer = stack.peek();
      TreeNode node = (TreeNode) enumer.nextElement();
      Enumeration children = node.children();

      if (!enumer.hasMoreElements()) {
        stack.pop();
      }
      if (children.hasMoreElements()) {
        stack.push(children);
      }
      return node;
    }

  }  // End of class PreorderEnumeration


  final class PostorderEnumeration implements Enumeration<TreeNode> {

    protected TreeNode root;
    protected Enumeration<TreeNode> children;
    protected Enumeration<TreeNode> subtree;

    public PostorderEnumeration(TreeNode rootNode) {
      super();
      root = rootNode;
      children = root.children();
      subtree = EMPTY_ENUMERATION;
    }

    public boolean hasMoreElements() {
      return root != null;
    }

    public TreeNode nextElement() {
      TreeNode retval;

      if (subtree.hasMoreElements()) {
        retval = subtree.nextElement();
      } else if (children.hasMoreElements()) {
        subtree = new PostorderEnumeration(children.nextElement());
        retval = subtree.nextElement();
      } else {
        retval = root;
        root = null;
      }

      return retval;
    }

  }  // End of class PostorderEnumeration


  final class BreadthFirstEnumeration implements Enumeration<TreeNode> {

    protected Queue queue;

    public BreadthFirstEnumeration(TreeNode rootNode) {
      super();
      Vector<TreeNode> v = new Vector<TreeNode>(1);
      v.addElement(rootNode);     // PENDING: don't really need a vector
      queue = new Queue();
      queue.enqueue(v.elements());
    }

    public boolean hasMoreElements() {
      return (!queue.isEmpty() &&
          ((Enumeration) queue.firstObject()).hasMoreElements());
    }

    public TreeNode nextElement() {
      Enumeration enumer = (Enumeration) queue.firstObject();
      TreeNode node = (TreeNode) enumer.nextElement();
      Enumeration children = node.children();

      if (!enumer.hasMoreElements()) {
        queue.dequeue();
      }
      if (children.hasMoreElements()) {
        queue.enqueue(children);
      }
      return node;
    }


    // A simple queue with a linked list data structure.
    final class Queue {

      QNode head; // null if empty
      QNode tail;

      final class QNode {

        public Object object;
        public QNode next;   // null if end

        public QNode(Object object, QNode next) {
          this.object = object;
          this.next = next;
        }
      }

      public void enqueue(Object anObject) {
        if (head == null) {
          head = tail = new QNode(anObject, null);
        } else {
          tail.next = new QNode(anObject, null);
          tail = tail.next;
        }
      }

      public Object dequeue() {
        if (head == null) {
          throw new NoSuchElementException("No more elements");
        }

        Object retval = head.object;
        QNode oldHead = head;
        head = head.next;
        if (head == null) {
          tail = null;
        } else {
          oldHead.next = null;
        }
        return retval;
      }

      public Object firstObject() {
        if (head == null) {
          throw new NoSuchElementException("No more elements");
        }

        return head.object;
      }

      public boolean isEmpty() {
        return head == null;
      }

    } // End of class Queue

  }  // End of class BreadthFirstEnumeration


  final class PathBetweenNodesEnumeration implements Enumeration<TreeNode> {

    protected Stack<TreeNode> stack;

    public PathBetweenNodesEnumeration(TreeNode ancestor,
        TreeNode descendant) {
      super();

      if (ancestor == null || descendant == null) {
        throw new IllegalArgumentException("argument is null");
      }

      TreeNode current;

      stack = new Stack<TreeNode>();
      stack.push(descendant);

      current = descendant;
      while (current != ancestor) {
        current = current.getParent();
        if (current == null && descendant != ancestor) {
          throw new IllegalArgumentException("node " + ancestor +
              " is not an ancestor of " + descendant);
        }
        stack.push(current);
      }
    }

    public boolean hasMoreElements() {
      return stack.size() > 0;
    }

    public TreeNode nextElement() {
      try {
        return stack.pop();
      } catch (EmptyStackException e) {
        throw new NoSuchElementException("No more elements");
      }
    }

  } // End of class PathBetweenNodesEnumeration


} // End of class DefaultMutableTreeNode
